package class10;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class Union_Find2 {

    public static class Node<V>{
        V value;

        public Node(V v){
            value = v;
        }
    }

    public  static class UnionFind<V>{
        public HashMap<V,Node<V>> nodes;
        public HashMap<Node<V>,Node<V>> parents;
        public HashMap<Node<V>,Integer> sizeMap;

        public UnionFind(List<V> values){
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values){
                Node<V> node = new Node<>(cur);
                nodes.put(cur,node);
                parents.put(node,node);
                sizeMap.put(node,1);
            }
        }

        public Node<V> findFather(Node<V> cur){
            Stack<Node<V>> path = new Stack<>();
            while (cur!=parents.get(cur)){
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty())
                parents.put(path.pop(),cur);
            return cur;
        }

        public boolean isSameSet(V a,V b){
            if (!nodes.containsKey(a) || !nodes.containsKey(b))
                return false;
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a,V b){
            if (!nodes.containsKey(a) || !nodes.containsKey(b))
                return;
            Node<V> ahead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (ahead != bHead){
                int aSetSize = sizeMap.get(ahead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >bSetSize ? ahead:bHead;
                Node<V> small = big ==ahead?bHead:ahead;
                parents.put(small,big);
                sizeMap.put(big,aSetSize+bSetSize);
                sizeMap.remove(small);
            }
        }

        public int sets(){
            return sizeMap.size();
        }
    }
}
